//给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 
//
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 
//
// 
//
// 示例: 
//
// 输入："23"
//输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
// 
//
// 说明: 
//尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。 
// Related Topics 字符串 回溯算法 
// 👍 825 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//Java：电话号码的字母组合
public class P17LetterCombinationsOfAPhoneNumber {

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * 思路: 网上的答案是递归和回朔，有点看不懂。然后看到有人说动态规划，就试着做了一下。
     *
     *   先创建数组 dp，  dp[i] 代表 i+1 个长度的字符串表示的组合，题目要求digits的组合，就是 dp[digits.length() - 1]
     *   然后 发现规律，dp[i] = dp[i - 1] 再拼上digits.charAt(i)的三种可能，结果就出来了
     *
     * 执行用时： 7 ms , 在所有 Java 提交中击败了 34.12% 的用户 内存消耗： 39.8 MB , 在所有 Java 提交中击败了 40.41% 的用户
     */
    class Solution {
        private Map<Character, String> map = new HashMap<>();

        //  2333
        public List<String> letterCombinations(String digits) {
            if (digits.isEmpty()) {
                return new ArrayList<>();
            }
            // dp[i] 代表 i+1 个长度的字符串表示的组合
            List<String>[] dp = new List[digits.length()];

            List<String> zero = new ArrayList<>();
            for (int c = 0; c < getValue(digits.charAt(0)).length(); c++) {
                zero.add(String.valueOf(getValue(digits.charAt(0)).charAt(c)));
            }
            dp[0] = zero;

            // dp[i] = 3 * dp[i - 1]
            for (int i = 1; i < digits.length(); i++) {
                List<String> dpList = new ArrayList<>();
                String str = getValue(digits.charAt(i));
                for (String pre : dp[i - 1]) {
                    for (int k = 0; k < str.length(); k++) {
                        dpList.add(pre + str.charAt(k));
                    }
                }
                dp[i] = dpList;
            }
            return dp[digits.length() - 1];

        }

        private String getValue(char ch) {
            if (map.isEmpty()) {
                map.put('2', "abc");
                map.put('3', "edf");
                map.put('4', "ghi");
                map.put('5', "jkl");
                map.put('6', "mno");
                map.put('7', "pqrs");
                map.put('8', "tuv");
                map.put('9', "wxyz");
            }
            return map.get(ch);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P17LetterCombinationsOfAPhoneNumber().new Solution();
        System.out.println(solution.letterCombinations("23"));
        // TO TEST
    }

}